package com.gxc.string;

/**
 * 给定两个字符串str1和str2，再给定三个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，
 * 返回将str1编辑成str2的最小代价。
 * [举例]
 * str1="abc"，str2="adc"，ic=5，dc=3，rc=2
 * 从"abc"编辑成"adc"，把 'b'替换成'd' 是代价最小的，所以返回2
 * str1="abc"，str2="adc",ic=5，dc=3，rc=100
 * 从"abc"编辑成"adc"，先删除'b'，然后插入'd' 是代价最小的，所以返回8
 * str1="abc"，str2="abc",ic=5，dc=3，rc=2
 * 不用编辑了，本来就是一样的字符串，所以返回0
 *
 * 解法：
 * dp[i][j]代表str1[0..i] -> str2[0..j]的最小代价
 * 1、【不操作】当str1[i - 1] == str2[i - 1]，
 * 说明str1[0..i-1] -> str2[0..j-1]只需要str1[0..i-2] 编辑成 str2[0..j-2]的代价，也就是dp[i - 1][j - 1]
 * 2、【删除】先把str1[0~i-2] 编辑成 str2[0~j-1]，那么就删除str[i-1]，因此此时花销为dp[i - 1][j] + dc
 * 3、【插入】先把str1[0~i-1] 编辑成 str2[0~j-2]，那么插入一个字符，使之相等，因此此时花销为ic + dp[i][j - 1]
 * 4、【替换】先把str1[i - 2] 编辑成 str2[j - 2]，那么直接替换str1[i - 1]，使之相等，因此此时花销为dp[i - 1][j - 1] + rc
 *
 */
public class MinimumCost {

    public static void main(String[] args) {
        String str1="abc";
        String str2="adc";
        int ic=5;
        int dc=3;
        int rc=2;
        System.out.println(process(str1, str2, ic, dc, rc));

        str1="abc";
        str2="adc";
        ic=5;
        dc=3;
        rc=100;
        System.out.println(process(str1, str2, ic, dc, rc));

        str1="abc";
        str2="abc";
        ic=5;
        dc=3;
        rc=2;
        System.out.println(process(str1, str2, ic, dc, rc));
    }

    public static int process(String str1, String str2, int ic, int dc, int rc) {
        if (str1 == null && str2 == null) return 0;

        //加1  是因为  "" -> "" "a" -> "" dc
        int length1 = str1.length()+1;
        int length2 = str2.length()+1;
        int[][] dp = new int[length1][length2];

        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        //str1[0..i] -> ""
        for (int row = 0; row < length1; row++) {
            dp[row][0] = dc * row;
        }
        //"" -> str1[0..j]
        for (int col = 0; col < length2; col++) {
            dp[0][col] = ic * col;
        }
        for (int row = 1; row < length1; row++) {
            for (int col = 1; col < length2; col++) {
                if (chars1[row-1] == chars2[col-1]) {
                    dp[row][col] = dp[row-1][col-1];
                } else {
                    dp[row][col] = dp[row-1][col-1] + rc;
                }
                dp[row][col] = Math.min(dp[row][col], Math.min(dp[row-1][col] + dc, dp[row][col-1]+ ic));
            }
        }

        return dp[length1-1][length2-1];
    }

}
